// https://leetcode.cn/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
private:
    pair<int, int> nextXY(int k, int n) {
        int x = (k - 1) / n, y = (k - 1) % n;
        if (x % 2 == 1) {
            y = n - 1 - y;
        }
        return {n - 1 - x, y};
    }

public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        vector<bool> visited(n * n + 1, false);
        queue<pair<int, int>> q;
        q.push({1, 0});
        visited[1] = true;

        while (!q.empty()) {
            int frontPos = q.front().first;
            int frontStep = q.front().second;
            q.pop();

            for (int i = 1; i <= 6; i++) {
                int nxt = frontPos + i;
                if (nxt > n * n) {
                    break;
                }

                int x = nextXY(nxt, n).first, y = nextXY(nxt, n).second;
                if (board[x][y] != -1) {
                    nxt = board[x][y];
                }

                if (nxt == n * n) {
                    return frontStep + 1;
                }

                if (!visited[nxt]) {
                    visited[nxt] = true;
                    q.push({nxt, frontStep + 1});
                }
            }
        }

        return -1;
    }
};